package mo.offer_version2;


import java.util.HashMap;
import java.util.Map;

public class L35 {

    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Node cur = head;
        Map<Node, Node> ori2copy = new HashMap<>();
        while (cur != null) {
            Node node = new Node(cur.val);
            ori2copy.put(cur, node);
            cur = cur.next;
        }
        cur = head;
        while (cur != null) {
            Node node = ori2copy.get(cur);
            if (cur.next != null) {
                node.next = ori2copy.get(cur.next);
            }
            if (cur.random != null) {
                node.random = ori2copy.get(cur.random);
            }
            cur = cur.next;
        }
        return ori2copy.get(head);
    }


    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

}
